/**
 * 对于最长回文串，我们还可以使用 DP 的方法来解决,
 * 因为回文串从性质上天然支持条件转移：
 * 如果一个字符串是回文串，那么即使去掉左右两边的字符串后，其【子串】仍然是一个回文串
 * - 区分【子串】和【子序列】
 *  - 子串是指连续的子序列
 *  - 子序列是指任意地选取的，只需要满足相对的顺序的子字符串
 * 状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
 * dp[i][j] 用来表示序列 i~j 的子串是否为回文串
 */
#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
  string longestPalindrome(string s) {
    if (s.size() <= 1)
      return s;
    // bool **dp = new bool *[s.size()];
    vector<vector<int>> dp(s.size(), vector<int>(s.size()));
    int start = 0, maxLen = 1;

    for (int i = 0; i < s.length(); i++) {
      dp[i][i] = 1;
    }
    // 先遍历列，再遍历行
    for (int j = 1; j < s.length(); ++j) {
      for (int i = 0; i < j; ++i) {
        if (s[i] != s[j]) {
          dp[i][j] = 0;
        } else {
          if (j - i < 3) {
            dp[i][j] = 1;
          } else {
            dp[i][j] = dp[i + 1][j - 1];
          }
        }

        if (dp[i][j] && j - i + 1 > maxLen) {
          start = i;
          maxLen = j - i + 1;
        }
      }
    }

    return s.substr(start, maxLen);
  }
};

int main() {
  Solution *s = new Solution;
  string str = s->longestPalindrome("ac");
  cout << str << endl;

  return 0;
}